#include<iostream>

using namespace std;

struct Node {
    int value;
    Node * left;
    Node * right;
};

Node* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);

Node * ConstructCore(int * preOrder, int * inOrder , int length){
    if ( preOrder == nullptr || inOrder == nullptr || length <=0 )
        return nullptr;
    return ConstructCore(preOrder, preOrder+length-1, inOrder, inOrder + length -1);
}

Node * ConstructCore(int * startPreOrder, int * endPreOrder, int * startInOrder, int * endInOrder){
    // 创建根节点
    Node * root = new Node();
    int rootValue = *startPreOrder;
    root -> value = rootValue;
    root -> left = root -> right =  nullptr;

    if ( startPreOrder == endPreOrder ){
        if ( startInOrder == endInOrder && *startPreOrder == *startInOrder ){
            return root;
        }
    }

    // 在中序遍历中查找根节点的下标
    int * findRootIndex = startInOrder;
    while ( findRootIndex <= endInOrder && rootValue != * findRootIndex ){
            findRootIndex ++;
    }
    int leftLength = findRootIndex - startInOrder;
    if ( leftLength > 0 ){
        // 构建左子树
        root -> left = ConstructCore(startPreOrder+1, startPreOrder+leftLength, startInOrder, findRootIndex-1);
    }
    if ( leftLength < endPreOrder - startPreOrder ){
        // 构建右子树
        root -> right = ConstructCore(startPreOrder+1+leftLength, endPreOrder, findRootIndex+1, endInOrder);
    }
    return root;
}

void PreOrderTraverse(Node * head){
    if ( head == nullptr ) {
	return;
    }
    cout << head->value << "  ";
    PreOrderTraverse(head->left);
    PreOrderTraverse(head->right);
}

int main(void){
    int length = 8;
    int preorder[length] = {1, 2, 4, 7, 3, 5, 6, 8};
    int inorder[length] = {4, 7, 2, 1, 5, 3, 8, 6};
    Node * root = ConstructCore(preorder, inorder, length);
    PreOrderTraverse(root);
    return 0;
}